#include<bits/stdc++.h>
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
constexpr int mod = 998244353;
inline void add(int &x) { x >= mod && ( x -= mod ); }
inline void sub(int &x) { x < 0 && ( x += mod ); }
inline int qpow(int x, int y) { int z = 1; while ( y ) y & 1 && ( z = (ll)z * x % mod ), ( y >>= 1 ) && ( x = (ll)x * x % mod ); return z; }
inline int inv(int x) { return qpow(x, mod - 2); }
int fac[6009], ifac[6009];
inline void init(int n)
{
	fac[0] = 1; For(i, 1, n) fac[i] = (ll)i * fac[i - 1] % mod;
	ifac[n] = inv(fac[n]); Fol(i, n, 1) ifac[i - 1] = (ll)i * ifac[i] % mod;
}
inline int c(int x, int y) { return x >= y && y >= 0 ? (ll)fac[x] * ifac[y] % mod * ifac[x - y] % mod : 0; }
constexpr int inf = numeric_limits < int >::max() >> 1;
int cid, n, m, u[4000009], v[4000009];
namespace BF
{
	int eu[19], ev[19], ec, dis[19][19], res, mn, ans; bool ok;
	vector < int > g[19]; queue < int > q;
	inline void slv()
	{
		mn = inf, ec = ans = 0;
		For(i, 1, n) For(j, i + 1, n) eu[ec] = i, ev[ec++] = j;
		For(s, 0, ( 1 << ec ) - 1) if ( __builtin_popcount(s) == m - 1 )
		{
			For(i, 1, n) g[i].clear();
			For(i, 0, ec - 1) if ( s & ( 1 << i ) )
				g[eu[i]].push_back(ev[i]), g[ev[i]].push_back(eu[i]);
			For(i, 1, n)
			{
				fill(dis[i] + 1, dis[i] + n + 1, inf), dis[i][i] = 0, q.push(i);
				for ( int u ; q.size() ; )
				{
					u = q.front(), q.pop();
					for ( int v : g[u] ) if ( dis[i][v] > dis[i][u] + 1 )
						dis[i][v] = dis[i][u] + 1, q.push(v);
				}
			}
			res = 0, ok = true;
			For(i, 1, m) if ( dis[u[i]][v[i]] == inf ) { ok = false; break; }
			if ( !ok ) continue;
			For(i, 1, m) res += dis[u[i]][v[i]];
			if ( res < mn ) mn = res, ans = 1; else if ( res == mn ) ans++;
		}
		cout << '-' << mn << ' ' << ans << '\n';
	}
}
int fa[2009], fw[2009], dep[2009], bel[2009], mn, o, deg[2009], ok[4000009]; bool used[4000009];
vector < pair < int, int > > g[2009]; queue < int > q; vector < int > ps; map < int, int > mp;
inline void go(int u) { while ( fa[u] ) { if ( ok[fw[u]] == mn ) return; ok[fw[u]] = mn, u = fa[u]; } }
inline int calc(int x) { return (ll)c(x * 3 - 3, x - 1) * inv(x * 2 - 1) % mod; }
inline void work()
{
	cin >> n >> m, mn = inf, fill(ok + 1, ok + m + 1, 0);
	For(i, 1, m) cin >> u[i] >> v[i];
	if ( cid <= 2 ) { BF::slv(); return; }
	For(i, 1, n) g[i].clear();
	For(i, 1, m) g[u[i]].emplace_back(v[i], i), g[v[i]].emplace_back(u[i], i);
	For(i, 1, n)
	{
		fill(dep + 1, dep + n + 1, inf), fill(used + 1, used + m + 1, false);
		fa[i] = fw[i] = dep[i] = bel[i] = 0, q.push(i);
		for ( int u ; q.size() ; )
		{
			u = q.front(), q.pop();
			for ( auto [v, id] : g[u] ) if ( dep[v] > dep[u] + 1 ) fa[v] = u, fw[v] = id,
				dep[v] = dep[u] + 1, bel[v] = bel[u] ? bel[u] : v, q.push(v), used[id] = true;
		}
		For(j, 1, m) if ( !used[j] && bel[u[j]] != bel[v[j]] )
		{
			mn = min(mn, o = dep[u[j]] + dep[v[j]] + 1);
			if ( mn == o ) ok[j] = mn, go(u[j]), go(v[j]);
		}
	}
	o = 0; For(i, 1, m) o += ok[i] == mn;
	cout << '-' << mn + m - 2 << ' ' << (ll)calc(mn) * inv(mn) % mod * o % mod << '\n';
}
int main()
{
	freopen("oi.in", "r", stdin), freopen("oi.out", "w", stdout);
	cin.tie(nullptr) -> sync_with_stdio(false);
	int t; init(6000), cin >> cid >> t; while ( t-- ) work(); return 0;
}